package craft;

/**
 * 简单的语法解析器
 * 能够解析简单的表达式、变量声明和初始化语句、赋值语句
 * 支持的语法规则：
 * program -> intDeclare | expressionStatement | assignmentStatement
 * intDeclare -> 'int' Id ( = additive) ';'
 * expressionStatement -> addtive ';'
 * assignmentStatement -> Identifier '=' additive ';'
 * addtive -> multiplicative ( (+ | -) multiplicative)*
 * multiplicative -> primary ( (* | /) primary)*
 * primary -> IntLiteral | Id | (additive)
 */

public class SimpleParser {
    public static void main(String[] args) {
        SimpleParser parser =new SimpleParser();
        String script = null;
        ASTNode tree = null;

        try {
            script = "int age = 45+2; age= 20; age+10*2;";
            System.out.println("解析："+script);
            tree = parser.parse(script);
            parser.dumpAST(tree, "");
        } catch (Exception e) {

            System.out.println(e.getMessage());
        }

        //测试异常语法
        try {
            script = "2+3+;";
            System.out.println("解析："+script);
            tree = parser.parse(script);
            parser.dumpAST(tree, "");
        } catch (Exception e) {
            System.out.println(e.getMessage());
        }

        //测试异常语法
        try {
            script = "2+3*;";
            System.out.println("解析："+script);
            tree = parser.parse(script);
            parser.dumpAST(tree, "");
        } catch (Exception e) {
            System.out.println(e.getMessage());
        }
    }

    /**
     * 打印AST所有子节点
     * @param node
     * @param indent
     */
    void dumpAST(ASTNode node, String indent) {
        System.out.println(indent + node.getType() + " " + node.getText());
       for (ASTNode child : node.getChildren()) {
           dumpAST(child, indent);
       }
    }

    /**
     * 执行脚本，并打印AST和求值过程
     * @param script
     */
    private void evaluate(String script) {
        try {
            ASTNode tree = parse(script);
            dumpAST(tree, "");
            evaluate(tree, "");
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    /**
     * 对某个AST节点求值，并打印求值过程
     * @param node
     * @param indent
     */
    private int evaluate(ASTNode node, String indent) {
        int result = 0;

        System.out.println(indent + "Calculating: " + node.getType());

        switch(node.getType()) {
            case Program:
                for (ASTNode child : node.getChildren()) {
                    result = evaluate(child, indent + "\t");
                }
                break;
            case Additive:
                SimpleASTNode child1 = (SimpleASTNode) node.getChildren().get(0);
                int value1 = evaluate(child1, indent + "\t");
                SimpleASTNode child2 = (SimpleASTNode) node.getChildren().get(1);
                int value2 = evaluate(child2, indent + "\t");
                if (node.getText().equals("+")) {
                    result = value1 + value2;
                } else if (node.getText().equals("-")) {
                    result = value1 - value2;
                }
                break;
            case Multiplicative:
                child1 = (SimpleASTNode) node.getChildren().get(0);
                value1 = evaluate(child1, indent + "\t");
                child2 = (SimpleASTNode) node.getChildren().get(1);
                value2 = evaluate(child2, indent + "\t");
                if (node.getText().equals("*")) {
                    result = value1 * value2;
                } else if (node.getText().equals("/")) {
                    result = value1 / value2;
                }
                break;
            case IntDeclaration:
                result = Integer.valueOf(node.getText()).intValue();
        }

        System.out.println(indent + "Result: " + result);

        return result;
    }

    /**
     * 解析脚本，并返回根节点
     * @param script
     * @return
     */
    ASTNode parse(String script) throws Exception {
        SimpleLexer lexer = new SimpleLexer();
        TokenReader tokens = lexer.tokenize(script);

        ASTNode node = prog(tokens);
        return node;
    }

    /**
     * 解析token流，构建AST，并返回根节点
     * programm -> intDeclare | expressionStatement | assignmentStatement
     * @param tokens
     * @return
     */
    private ASTNode prog(TokenReader tokens) throws Exception {
        SimpleASTNode node = new SimpleASTNode(ASTNodeType.Program, "pwc");

        while (tokens.peek() != null) {
            SimpleASTNode child = intDeclare(tokens);

            if (child == null) {
                child = expressionStatement(tokens);
            }

            if (child == null) {
                child = assignmentStatement(tokens);
            }

            if (child != null) {
                node.addChild(child);
            } else {
                throw new Exception("unknown statement");
            }
        }
        return node;
    }

    /**
     * 赋值语句
     * assignmentStatement -> Identifier '=' additive ';'
     * 例如：age = 10*2;
     * @param tokens
     * @return
     */
    private SimpleASTNode assignmentStatement(TokenReader tokens) throws Exception {
        Token token = null;
        SimpleASTNode node = null;
        token = tokens.peek();
        // 预读，检查是否为标识符
        if (token != null && token.getType() == TokenType.Identifier) {
            // 消耗 标识符
            token = tokens.read();
            node = new SimpleASTNode(ASTNodeType.AssignmentStmt, token.getText());
            // 预读，检查是否为等号
            token = tokens.peek();
            if (token != null && token.getType() == TokenType.Assignment) {
                // 读入 等号
                token = tokens.read();
                SimpleASTNode child = additive(tokens);
                if (child != null) {
                   node.addChild(child);
                   token = tokens.peek();
                   if (token != null && token.getType() == TokenType.SemiColon) {
                       // 分号 直接消耗掉
                       token = tokens.read();
                   }
                } else {
                    throw new Exception("invalid assignment statement, expecting an expression");
                }
            } else {
                // 出错，回溯，吐出之前消耗的token
                tokens.unread();
                node = null;
            }
        }
        return node;
    }

    /**
     * 表达式语句：一个additive 加 一个 分号
     * expressionStatement -> addtive ';'
     * @param tokens
     * @return
     */
    private SimpleASTNode expressionStatement(TokenReader tokens) throws Exception {
        // 记下位置，以便出错时回溯
        // 这里还要注意，要先在additive之前获得pos的值，否则additive会改变pos的值
        int pos = tokens.getPosition();
        // 先预读一个token
        Token token = null;
        SimpleASTNode child1 = additive(tokens);
        SimpleASTNode node = child1;

        if (child1 != null) {
            token = tokens.peek();
            if (token != null && token.getType() == TokenType.SemiColon) {
                token = tokens.read();
            } else {
                // 千万别忘了 要把node置为null
                node = null;
               tokens.setPosition(pos);
            }
        }
        return node;
    }

    /**
     * 解析是否满足整形变量声明语句
     * 如：int a;
     *     int b = 2 * 3;
     *
     * @param tokens
     * @return
     */
    private SimpleASTNode intDeclare(TokenReader tokens) throws Exception {
        // 先预读一个token
        Token token = tokens.peek();
        SimpleASTNode node = null;
        // 尝试匹配int
        if (token != null && token.getType() == TokenType.Int) {
            // 消耗掉int
            tokens.read();
            token = tokens.peek();
            // 尝试匹配标识符
            if (token != null && token.getType() == TokenType.Identifier) {
                // 消耗掉标识符
                tokens.read();
                // 创建节点，并保存变量名到当前节点的文本值中
                node = new SimpleASTNode(ASTNodeType.IntDeclaration, token.getText());
                token = tokens.peek();
                if (token != null && token.getType() == TokenType.Assignment) {
                    // 消耗掉 赋值等号
                    token = tokens.read();
                    SimpleASTNode child = additive(tokens);      // 匹配表达式
                    if (child == null) {
                        throw new Exception("Invalid variable initialization, expecting an expression");
                    } else {
                        node.addChild(child);
                    }
                }
            } else {
                throw new Exception("variable name expected");
            }

            if (node != null) {
                token = tokens.peek();
                if (token != null && token.getType() == TokenType.SemiColon) {
                    // 消耗 逗号
                    tokens.read();
                } else {
                    throw new Exception("Invalid statement, expecting semicolon");
                }
            }
        }
        return node;
    }

    /**
     * 匹配 加法表达式
     * 这里 加减本质一样，乘除本质一样
     * 这里使用了循环来替代左递归
     * addtive -> multiplicative ( (+ | -) multiplicative)*
     * multiplicative -> primary ( (* | /) primary)*
     * primary -> IntLiteral | Id | (additive)
     * @param tokens
     * @return
     */
    private SimpleASTNode additive(TokenReader tokens) throws Exception {
        SimpleASTNode child1 = multiplicative(tokens);
        SimpleASTNode node = child1;
        Token token = null;

        if (child1 != null) {
            while (true) {
                // 预读，判断是否为 加号 或者 减号
                token = tokens.peek();
                if (token != null && token.getType() == TokenType.Plus || token.getType() == TokenType.Minus) {
                    token = tokens.read();
                    SimpleASTNode child2 = multiplicative(tokens);
                    if (child2 != null) {
                        node = new SimpleASTNode(ASTNodeType.Additive, token.getText());
                        node.addChild(child1);
                        node.addChild(child2);
                    } else {
                        throw new Exception("invalid additive expression, expecting the right part");
                    }
                } else {
                    // token读完
                    break;
                }
            }
        }
        return node;
    }


    /**
     * 匹配 乘法表达式
     * multiplicative -> primary | primary * multiplicative
     * @param tokens
     * @return
     */
    private SimpleASTNode multiplicative(TokenReader tokens) throws Exception {
        SimpleASTNode child1 = primary(tokens);
        SimpleASTNode node = child1;

        Token token = tokens.peek();
        if (child1 != null && token != null) {
            // 尝试匹配 乘号 或者 除号
            if (token.getType() == TokenType.Star || token.getType() == TokenType.Slash) {
                // 消耗 乘号 或者 除号
                tokens.read();
                SimpleASTNode child2 = multiplicative(tokens);
                if (child2 != null) {
                    node = new SimpleASTNode(ASTNodeType.Multiplicative, token.getText());
                    node.addChild(child1);
                    node.addChild(child2);
                } else {
                    throw new Exception("invalid multiplicative expression, expecting the right part.");
                }
            }
        }
        return node;
    }


    /**
     * 匹配 基础表达式
     * primary -> IntLiteral | Identifier | '(' additive ')'
     * @param tokens
     * @return
     */
    private SimpleASTNode primary(TokenReader tokens) throws Exception {
        SimpleASTNode node = null;
        Token token = tokens.peek();
        if (token != null && token.getType() == TokenType.IntLiteral) {
            tokens.read();
            node = new SimpleASTNode(ASTNodeType.IntLiteral, token.getText());
        } else if (token != null && token.getType() == TokenType.Identifier) {
            tokens.read();
            node = new SimpleASTNode(ASTNodeType.Identifier, token.getText());
        } else if (token != null && token.getType() == TokenType.LeftParen) {
            tokens.read();
            node = additive(tokens);
            if (node != null) {
                token = tokens.read();
                if (token != null && token.getType() == TokenType.RightParen) {
                    tokens.read();
                } else {
                    throw new Exception("expecting right parenthesis");
                }
            } else {
                throw new Exception("expecting an additive expression inside parenthesis");
            }
        }
        return node;
    }
}
